Many communications systems comprise centralised servers operated by a system provider. A client may obtain services by accessing one of those servers. Typically, the server authenticates the client's identity before providing it with the requested services. For example, the user may be required to enter a user name and password that the server checks against a record of user names and passwords that it stores or has access to. Once the server has authenticated the client, it may provide the services as requested.
Other communication systems are arranged differently. Instead of using only centralised servers that are operated by the system provider, the network may contain a large number of distributed nodes that a client can access to obtain services. These nodes are not necessarily either owned or operated by the system provider. For example, the nodes may be user devices running software from the system provider that enables them to act as nodes in the communication system. This enables a communication system to be created by essentially “borrowing” a small amount of computing resources from millions of devices. A user can then access the system via any one of millions of nodes.
In such distributed networks, it is no longer necessary for a client to access a centralised server to obtain services. However, the need to authenticate the client remains.
One option would be for the client to provide the distributed node with its username and password, which the distributed node can then check with a centralised database. However, it is undesirable for a distributed node to have to contact a centralised database every time it needs to authenticate a client. An alternative option is to assign each client a private/public key pair. The client can authenticate itself with the distributed node by sending the node a message that it has digitally signed with its private key. The distributed node can then authenticate the client by applying the corresponding public key to the message.
Each client is typically issued with a digital certificate. Digital certificates form part of the RELOAD protocol and are described in “Resource Location and Discovery (RELOAD) Base Protocol” by C. Jennings et al. The certificates contain a binding between a username and a public key so that a third party node can be sure that the public key is assigned to that particular client. The certificates may be issued by the central server, which is trusted by the nodes, or by some trusted third party issuer. The issuer signs the certificate with its private key. Because the node trusts the issuer of the certificate, it can be sure that the client's public key is assigned to the client once it has the certificate authenticating that key.
Typically a certificate includes:                The client's public key        The client's username        Expiration date of the certificate        Name of the issuer        Digital signature of the issuer        
In a large communication system it is not feasible for each node to store certificates for every user in the system. The certificates therefore need to be stored elsewhere in the system, in a location that is accessible by the distributed nodes. One option would be for the certificates to be stored by the central server. However, this would require the nodes to access that central server every time they want to authenticate a client. A preferred option is to store the certificates for a particular client in a particular node. The certificates can then be distributed throughout the nodes of the communication system.
An example of a distributed telecommunications system is shown in FIG. 1. The system, shown generally at 101, comprises a plurality of nodes, shown generally at 102. The system is pictured as a “ring” structure in which in each position in the ring is allocated a number. In the example shown in FIG. 1, the ring has 22 such positions. In reality, however, the number of positions may number many millions. Each position may be taken by a node, 102, with some positions remaining empty. A node that follows one or more empty positions will assume responsibility for the empty positions immediately preceding its own (e.g. the node 107 at position 20 in FIG. 1 also takes responsibility for positions 18 and 19, as illustrated at 103).
A certificate associated with a particular client may be stored in one of the nodes. In FIG. 1 the certificate authenticating the public key of client 104 is stored in node 106. Typically the identity of the nodes that will store a certificate associated with one particular user will be determined by a central server, which can then ‘push’ the certificates out to the appropriate nodes. A node that wants to authenticate a particular client can request that client's certificate from the node that stores it.
One way of storing data in a communication system comprising a large number of distributed nodes is by using a distributed hash table (DHT). A DHT provides a service similar to a hash table by storing key/value pairs so that any participating node can retrieve the value associated with a given key. A DHT may distribute responsibility for maintaining current mappings of keys to values among the nodes of a communication system so that a change in the participant nodes causes a minimal amount of disruption.
In order minimise the amount of data that nodes in the system are required to store for other nodes, any given node may only allowed to store data at a small number of locations within the overlay. For example, the RELOAD protocol provides access controls that permit a given key to be writable only by a small number of nodes. The locations to which a node is permitted to write may be determined by its certificate. The node may also be required to sign each value to be stored with its private key to authenticate its right to store at that location. Signing the value to be stored also serves to protect the stored data from tampering. It is therefore important to inform nodes in the overlay when a certificate is invalid not only to control access to the system but also to protect data stored within the system from rogue nodes.
One issue is how to revoke certificates before their expiration date. For example, if a user whose laptop is stolen will want to revoke that laptop's entitlement to access the communication system. In a communication system that may comprise many millions of nodes, this is not necessarily straightforward. One option is for a central server to push information regarding the revocation of certificates out to all of the nodes in the network. An example of this is the certificate revocation lists that are described in “Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile” by D. Cooper et al. However, if these messages are transmitted too frequently they can negatively impact the performance of the system. Conversely, if they are not transmitted frequently enough to provide the nodes with timely updates on certificate revocations, this leaves open the possibility that a client may be provided with services it is no longer entitled to because the node that stores its certificate has not been informed that the certificate has been revoked. Another option is to update nodes on certificate status by using online status checks, as described in “X.509 Internet Public Key Infrastructure Online Certificate Status Protocol—OCSP” by M. Myers et al. However, this requires nodes to contact a centralised OSCP responder (which may be the Certificate Authority) to check the current status of a certificate. This option therefore also suffers from a performance/timeliness trade-off whereby nodes seeking to obtain up-to-date certificate information can negatively impact system performance by bombarding a central node with status requests.
A further issue arises due to the way certificates are stored. In RELOAD, certificates are issued by a central authority and are then stored at a given location in the overlay (as described above). This location is writable by the owner of the certificate and hence is not secure from attack by compromised nodes.